/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date May 30, 2014
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @version 1.0
 * @description Sort a linked list in O(n log n) time using constant space
 *              complexity.
 */
public class SortList {

	class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	// Time limit exceeded
	public ListNode insertionSortList(ListNode head) {
		if (head == null)
			return head;
		ListNode res = new ListNode(Integer.MIN_VALUE);
		ListNode pre = res;
		pre.next = head;
		ListNode cur = head.next;
		ListNode cp = pre.next;
		ListNode next;
		while (cur != null) {
			pre = res; // previous node which need to be compared
			next = pre.next; // node which need to be compared
			while (cur.val > next.val) {
				pre = pre.next;
				next = next.next;
			}
			if (cur == next) {
				cur = cur.next; // current node need to be insert
				cp = cp.next; // previous node of cur
			} else {
				cp.next = cur.next;
				pre.next = cur;
				cur.next = next;
				cur = cp.next;
			}
		}

		return res.next;
	}

	void print(ListNode head) {
		while (head != null) {
			System.out.println(head.val);
			head = head.next;
		}
	}

	// another solution, also TLE
	public ListNode insertionSortList2(ListNode head) {
		if (head == null)
			return head;
		ListNode res = new ListNode(Integer.MIN_VALUE); // root node, previous
														// of head
		ListNode pre = res;
		ListNode cur = null;
		ListNode next;
		// use head to point the first node in unsorted list
		// use res.next to point the first node in sorted list
		while (head != null) {
			next = head; // next is the node need to insert
			head = head.next; // head of unsorted list
			next.next = null; // let next be a single node
			pre = res; // begin from res
			cur = pre.next; // the min node in sorted list
			while (cur != null && cur.val < next.val) { // find the insertion
														// position
				cur = cur.next;
				pre = pre.next;
			}
			pre.next = next; // insert
			next.next = cur;
		}
		return res.next;
	}

	// good job
	public ListNode quickSortList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}

		ListNode pivot = head;
		ListNode cur = head.next;

		ListNode bigHead = null;
		ListNode smallHead = null;
		ListNode bigIter = null;
		ListNode smallIter = null;
		ListNode pivotIter = pivot;

		while (null != cur) {
			ListNode iter = cur.next;

			if (cur.val > pivot.val) {
				if (bigHead == null) {
					bigHead = cur;
					bigIter = bigHead;
				} else {
					bigIter.next = cur;
					bigIter = bigIter.next;
				}
			} else if (cur.val == pivot.val) {
				pivotIter.next = cur;
				pivotIter = pivotIter.next;
			} else {
				if (smallHead == null) {
					smallHead = cur;
					smallIter = smallHead;
				} else {
					smallIter.next = cur;
					smallIter = smallIter.next;
				}
			}
			cur = iter;
		}

		// mark the ends for the big/small sub lists.
		if (smallIter != null) {
			smallIter.next = null;
		}

		pivotIter.next = null;

		if (bigIter != null) {
			bigIter.next = null;
		}

		ListNode sortBig = quickSortList(bigHead);
		ListNode sortSmall = quickSortList(smallHead);

		if (sortSmall == null) {
			pivotIter.next = sortBig;

			return pivot;
		} else {
			smallIter = sortSmall;
			while (smallIter.next != null) {
				smallIter = smallIter.next;
			}

			// reach the tail of the small sublist
			smallIter.next = pivot;
			// concatenate the two sublists.
			pivotIter.next = sortBig;

			return sortSmall;
		}
	}

	@Test
	public void test() {
		ListNode l1 = new ListNode(2);
		ListNode l2 = new ListNode(4);
		ListNode l3 = new ListNode(1);
		ListNode l4 = new ListNode(6);
		ListNode l5 = new ListNode(3);
		ListNode l6 = new ListNode(7);
		ListNode l7 = new ListNode(5);
		l1.next = l2;
		l2.next = l3;
		l3.next = l4;
		l4.next = l5;
		l5.next = l6;
		l6.next = l7;

		ListNode res = quickSortList(l1);
		print(res);
	}
}
